package com.offer;

public class treeDemo {
    public int lowestCommonAncestor3 (TreeNode root, int p, int q){

        while (root!=null){
            if (root.val<p&&root.val<q){
                root=root.right;
            }else if (root.val>p&&root.val>q){
                root=root.left;
            }else {
                break;
            }
        }
        return root.val;
    }
    public int lowestCommonAncestor2 (TreeNode root, int p, int q){

            if (root.val<p&&root.val<q){
                return lowestCommonAncestor2(root.right,p,q);
            }else if(root.val>p&&root.val>q){
                return lowestCommonAncestor2(root.left,p,q);
            }else {
                return root.val;
            }
    }
    public int lowestCommonAncestor (TreeNode root, int o1, int o2){
        if (root==null){
            return -1;
        }
        if (root.val==o1||root.val==o2){
            return root.val;
        }
        int l=lowestCommonAncestor(root.left,o1,o2);
        int r=lowestCommonAncestor(root.right,o1,o2);
        if (l==-1){
            return r;
        }else if (r==-1){
            return l;
        }else {
            return root.val;//当 left和 right均不为空时，说明 p、q节点分别在 root异侧, 最近公共祖先即为 root
        }
    }
    int k=0;
    public int FindPath (TreeNode root, int sum) {

        if (root==null){
            return 0;
        }
        sd(root,sum);
        FindPath(root.left,sum);
        FindPath(root.right,sum);
        return k;
    }
    public void sd(TreeNode root,int sum){
     if (root==null){
         return ;
     }
     sum=sum-root.val;
     if (sum==0){
         k++;
     }
     sd(root.left,sum);
     sd(root.right,sum);
    }
}
